package com.company.ljh.medium;

/**
 * @description:
 * 238. 除自身以外数组的乘积
 * 中等
 * 1.5K
 * 相关企业
 * 给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。
 *
 * 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在  32 位 整数范围内。
 *
 * 请不要使用除法，且在 O(n) 时间复杂度内完成此题。
 *
 * 进阶：你可以在 O(1) 的额外空间复杂度内完成这个题目吗？（ 出于对空间复杂度分析的目的，输出数组不被视为额外空间。）
 * @projectName:leet_code
 * @see:com.company.ljh.medium
 * @author:ljh
 * @createTime:2023/6/29 17:32
 * @version:1.0
 */
public class 除自身以外数组的乘积 {
    //**1.空间复杂度n法 ,分别计算每个数的前缀乘和后缀乘
    public static int[] productExceptSelf(int[] nums) {
        int [] prefix = new int[nums.length];
        int []suffix = new int[nums.length];
        int data = 1;
        prefix[0] = 1;
        suffix[nums.length - 1] = 1;
        for(int i = 1;i < nums.length ; i++){
            data *= nums[i - 1];
            prefix[i] = data;
        }
        data = 1;
        for(int i = nums.length-2;i >= 0 ; i--){
            data *= nums[i+1];
            suffix[i] = data;
        }
        int [] result = new int[nums.length];
        for(int i =0;i < nums.length;i++){
            result[i] = prefix[i] * suffix[i];
        }
        return result;
    }
    //**2.优化空间复杂度，只占用一个n长度的数组（输出数组不被视为额外空间）
    public static int[] productExceptSelf2(int[] nums) {
        //前缀乘法数组（复用为结果数组）
        int [] prefix = new int[nums.length];
        int data = 1;
        prefix[0] = 1;
        for(int i = 1;i < nums.length ; i++){
            data *= nums[i - 1];
            prefix[i] = data;
        }
        data = 1;
        for(int i = nums.length-2;i >= 0 ; i--){
            //动态生成后缀数组结果，并与前缀数组相乘求得结果
            data *= nums[i+1];
            prefix[i] *= data;
        }

        return prefix;
    }
    public static void main(String[] args) {
        int[] ints = productExceptSelf(new int[]{1, 2, 3, 4});
        int[] ints1 = productExceptSelf2(new int[]{1, 2, 3, 4});
        System.out.println(ints+"\n"+ints1);
    }
}
